package chapter12;

/**
 * 二叉搜索树
 */
public class TreeSearch {

    /**
     * 核心: 左边节点小于右边节点
     *
     * @param x
     * @param k
     * @return
     */
    public static Node treeSearch(Node x, int k) {
        if (x == null || x.key == k) {
            return x;
        }
        if (k < x.key) {
            return treeSearch(x.left, k);
        }
        return treeSearch(x.right, k);
    }

    public static Node iterativeTreeSearch(Node x, int k) {
        while (x != null && x.key != k) {
            if (k < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        return x;
    }

    /**
     * 最左边值就是最小
     *
     * @param x
     * @return
     */
    public static Node min(Node x) {
        while (x.left != null) {
            x = x.left;
        }
        return x;
    }

    /**
     * 最右边值就是最大
     *
     * @param x
     * @return
     */
    public static Node max(Node x) {
        while (x.right != null) {
            x = x.right;
        }
        return x;
    }

    /**
     * 后继
     * <p>
     * 当前节点右边节点不为null则递归找下去
     * <p>
     * 如果为空则找当前父节点的父节点的右节点
     *
     * @param x
     * @return
     */
    public static Node treeSuccessor(Node x) {
        if (x.right != null) {
            return treeSuccessor(x.right);
        }
        Node y = x.parent;
        while (y != null && x == y.right) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    /**
     * 前驱
     * <p>
     * 当前节点左边节点不为null则递归找下去
     * <p>
     * 如果为空则找当前父节点的父节点的左节点
     *
     * @param x
     * @return
     */
    public static Node treePredecessor(Node x) {
        if (x.left != null) {
            return treeSuccessor(x.left);
        }
        Node y = x.parent;
        while (y != null && x == y.left) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    /**
     * 插入节点
     *
     * @param T
     * @param z
     */
    public static void treeInsert(Node T, Node z) {
        // 父节点,z该挂在哪个节点下
        Node y = null;
        Node x = T.root;
        // 找到合适的节点
        while (x != null) {
            y = x;
            if (z.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
            z.parent = y;
        }
        // y为空说明root为null
        // 否则,z比当前y小挂左边,比y大挂右边
        if (y == null) {
            T.root = z;
        } else if (z.key < y.key) {
            y.left = z;
        } else {
            y.right = z;
        }
    }

    public static void transplant(Node T, Node v, Node u) {

    }

    public static void treeDelete(Node T, Node z) {
        // 如果是叶子节点,直接删除
        //
        if (z.left == null && z.right == null) {
            if (z.parent.left.key == z.key) {
                z.parent.left = null;
            } else {
                z.parent.right = null;
            }
        } else if (z.left == null) { // 如果左孩子为空,右孩子不为空
            // 将当前z的父节点给右孩子的父节点
            z.right.parent = z.parent;
            // 将当前z的右孩子给z的父节点右孩子
            z.parent.right = z.right;
            // 设置一下root
            z.parent.right.root = T.root;
        } else if (z.right == null) { // 同上,与上对称
            z.left.parent = z.parent;
            z.parent.right = z.left;
            z.parent.left.root = T.root;
        } else {
            // 找到z的最小节点y,讲z的左节点挂到y上
            // 因为z.left肯定是比z.right.left小,因为左边单调小于右边
            Node y = min(z.right);
            y.left = z.left;
            y.left.parent = y;

            // 将z.right挂到z.parent
            z.parent.right = z.right;
            z.right.parent = z.parent;
            z.right.root = T.root;
        }

    }

    public static class Node {
        public Node left;
        public int key;
        public Node right;
        public Node parent;
        public Node root;

        public Node() {
        }

        public Node(int key) {
            this.key = key;
        }
    }

}
